package com.kobe.game_40;

import java.math.BigDecimal;
import java.util.LinkedList;
import java.util.List;

/**
 * 
 * A unit fraction contains 1 in the numerator. The decimal representation of
 * the unit fractions with denominators 2 to 10 are given:
 * 
 * 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 =
 * 0.125 1/9 = 0.(1) 1/10 = 0.1
 * 
 * Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be
 * seen that 1/7 has a 6-digit recurring cycle.
 * 
 * Find the value of d 1000 for which 1/d contains the longest recurring cycle
 * in its decimal fraction part.
 * 
 * 
 */

/**
 * 备注： 首先 分数都为实数，即不存在无限不循环小数。（无限不循环小数是无理数）
 * 
 * 
 * result = 983
 */
public class Game26 {

    public static void main(String[] args) {
        int result = 0;
        int length = 0;
        for (int i = 2; i <= 1000; i++) {
            int cycleLength = findRecurringCycleLength(1, i);
            if (cycleLength != 0 && cycleLength > length) {
                length = cycleLength;
                result = i;
            }
        }
        System.out.println(result + " " + length);
    }

    private static int findRecurringCycleLength(int a, int b) {
        BigDecimal tempA = new BigDecimal(a);
        BigDecimal tempB = new BigDecimal(b);
        try {
            tempA.divide(tempB);
        } catch (ArithmeticException e) {
            return getRecurringCycleLength(a, b);
        }
        return 0;
    }

    private static int getRecurringCycleLength(int a, int b) {
        List<Integer> remainderArray = new LinkedList<Integer>();
        boolean found = false;

        int remainder = 0;
        while (!found) {
            remainder = a % b;
            if (remainder != 0) {
                int length = 0;
                if ((length = foundSameValue(remainderArray, remainder)) != 0) {
                    return length;
                } else {
                    a = remainder * 10;
                    remainderArray.add(remainder);
                }
            }
        }
        return 0;
    }

    private static int foundSameValue(List<Integer> remainderArray,
            int remainder) {
        for (int i = 0; i < remainderArray.size(); i++) {
            if (remainder == remainderArray.get(i)) {
                return remainderArray.size() - i;
            }
        }
        return 0;
    }

}
